/**
 * CS 2110 - Fall 2011 - Homework #11
 * Edited by: Brandon Whitehead
 *
 * list.c: Complete the functions!
 **/

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

/* The node struct.  Has a prev pointer, next pointer, and data. */
/* DO NOT DEFINE ANYTHING OTHER THAN WHAT'S GIVEN OR YOU WILL GET A ZERO*/
/* Design consideration only this file should know about nodes */
/* Only this file should be manipulating nodes */
typedef struct lnode
{
  struct lnode* prev; /* Pointer to previous node */
  struct lnode* next; /* Pointer to next node */
  void* data; /* User data */
} node;


/* Do not create any global variables here. Your linked list library should obviously work for multiple linked lists */
// This function is declared as static since you should only be calling this inside this file.
static node* create_node(void* data);

/** create_list
  *
  * Creates a list by allocating memory for it on the heap.
  * Be sure to initialize size to zero and head to NULL.
  *
  * @return an empty linked list
  */
list* create_list(void)
{
	list* list_p = malloc(sizeof(list));
	list_p->size = 0;
	list_p->head = NULL;
    return (list_p == NULL ? NULL : list_p);
}

/** create_node
  *
  * Helper function that creates a node by allocating memory for it on the heap.
  * Be sure to set its pointers to NULL.
  *
  * @param data a void pointer to data the user wants to store in the list
  * @return a node
  */
static node* create_node(void* data)
{
	node* node_p = malloc(sizeof(node));
	node_p->data = data;
	node_p->next = NULL;
	node_p->prev = NULL;
    return (node_p == NULL ? NULL : node_p);
}

/** push_front
  *
  * Adds the data to the front of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_front(list* llist, void* data)
{
	node* new_node = create_node(data);
	if(new_node == NULL)
	{
		return;
	}

	if(llist->size == 0)
	{
		llist->head = new_node;
		llist->head->next = llist->head;
		llist->head->prev = llist->head;
	}
	else
	{
		new_node->next = llist->head;
		new_node->prev = llist->head->prev;
		llist->head->prev->next = new_node;
		llist->head->prev = new_node;
		llist->head = new_node;
	}

	llist->size++;

}

/** push_back
  *
  * Adds the data to the back/end of the linked list
  *
  * @param llist a pointer to the list.
  * @param data pointer to data the user wants to store in the list.
  */
void push_back(list* llist, void* data)
{
	node* new_node = create_node(data);
	if(new_node == NULL)
	{
		return;
	}

	if(llist->size == 0)
	{
		llist->head = new_node;
		llist->head->next = llist->head;
		llist->head->prev = llist->head;
	}
	else
	{
		new_node->next = llist->head;
		new_node->prev = llist->head->prev;
		llist->head->prev->next = new_node;
		llist->head->prev = new_node;
	}

	llist->size++;
}

/** remove_front
  *
  * Removes the node at the front of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed (which is only there are no elements) 0 if the remove succeeded.
  */
int remove_front(list* llist, list_op free_func)
{
	if(llist->size == 0)
	{
		return -1;
	}

	node* temp_head = llist->head;
	llist->head->prev->next = llist->head->next;
	llist->head->next->prev = llist->head->prev;
	llist->head = llist->head->next;

	free_func(temp_head->data);
	free(temp_head);

	if(llist->size == 1) llist->head = NULL;
	llist->size--;
	return 0;


}

/** remove_index
  *
  * Removes the indexed node of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this
  * node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param index index of the node to remove.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed 0 if the remove succeeded.
  */
int remove_index(list* llist, int index, list_op free_func)
{
    /// @note Remember to also free the node itself
    /// @note free_func is a function that is responsible for freeing the node's data only.
	if((index >= llist->size) || (index < 0))
	{
		return -1;
	}
	node* cur_node = llist->head;
	int i = 0;
	while(i++ < index)
	{
		cur_node = cur_node->next;
	}


	if(cur_node == llist->head)
	{
		remove_front(llist, free_func);
	}
	else
	{
		node* to_del_node = cur_node;
		cur_node->prev->next = cur_node->next;
		cur_node->next->prev = cur_node->prev;

		free_func(to_del_node->data);
		free(to_del_node);

		llist->size--;
	}

	return 0;

}

/** remove_back
  *
  * Removes the node at the back of the linked list
  *
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list.
  * @param free_func pointer to a function that is responsible for freeing the node's data.
  * @return -1 if the remove failed 0 if the remove succeeded.
  */
int remove_back(list* llist, list_op free_func)
{
    /// @note Remember to also free the node itself
    /// @note free_func is a function that is responsible for freeing the node's data only.
	if(llist->size == 0)
	{
		return -1;
	}

	node* to_del_node = llist->head->prev;
	to_del_node->prev->next = to_del_node->next;
	to_del_node->next->prev = to_del_node->prev;

	free_func(to_del_node->data);
	free(to_del_node);

	if(llist->size == 1) llist->head = NULL;

	llist->size--;
	return 0;

    return -1;
}

/** remove_data
  *
  * Removes ALL nodes whose data is EQUAL to the data you passed in or rather when the comparison function returns true (!0)
  * @warning Note the data the node is pointing to is also freed. If you have any pointers to this node's data it will be freed!
  *
  * @param llist a pointer to the list
  * @param data data to compare to.
  * @param compare_func a pointer to a function that when it returns true it will remove the element from the list and do nothing otherwise @see equal_op.
  * @param free_func a pointer to a function that is responsible for freeing the node's data
  * @return the number of nodes that were removed.
  */
int remove_data(list* llist, const void* data, equal_op compare_func, list_op free_func)
{
    /// @note remember to also free all nodes you remove.
    /// @note free_func is a function that is responsible for freeing the node's data only.
	int numRemovedNodes = 0;
	node* cur_node = llist->head;
	for(int i = 0; i < llist->size; i++)
	{
		if(compare_func(cur_node->data, data))
		{
			node* to_del_node = cur_node;
			cur_node = cur_node->prev;

			if(to_del_node == llist->head) {
				remove_front(llist, free_func);
			}
			else
			{
				to_del_node->prev->next = to_del_node->next;
				to_del_node->next->prev = to_del_node->prev;

				free_func(to_del_node->data);
				free(to_del_node);
				llist->size--;

			}

			i--;
			numRemovedNodes++;
		}

		cur_node = cur_node->next;

	}
    return numRemovedNodes;
}

/** remove_if
  *
  * Removes all nodes whose data when passed into the predicate function returns true
  *
  * @param llist a pointer to the list
  * @param pred_func a pointer to a function that when it returns true it will remove the element from the list and do nothing otherwise @see list_pred.
  * @param free_func a pointer to a function that is responsible for freeing the node's data
  * @return the number of nodes that were removed.
  */
int remove_if(list* llist, list_pred pred_func, list_op free_func)
{
    /// @note remember to also free all nodes you remove.
    /// @note be sure to call pred_func on the NODES DATA to check if the node needs to be removed.
    /// @note free_func is a function that is responsible for freeing the node's data only.
	int numRemovedNodes = 0;
	node* cur_node = llist->head;
	for(int i = 0; i < llist->size; i++)
	{
		if(pred_func(cur_node->data)) {
			node* to_del_node = cur_node;
			cur_node = cur_node->prev;

			if(to_del_node == llist->head) {
				remove_front(llist, free_func);
			}
			else
			{
				to_del_node->prev->next = to_del_node->next;
				to_del_node->next->prev = to_del_node->prev;

				free_func(to_del_node->data);
				free(to_del_node);
				llist->size--;

			}

			i--;
			numRemovedNodes++;
		}

		cur_node = cur_node->next;

	}
	return numRemovedNodes;
}

/** front
  *
  * Gets the data at the front of the linked list
  * If the list is empty return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the first node in the linked list or NULL.
  */
void* front(list* llist)
{
    /// @note you are returning the HEAD's DATA not the head node. Remember the user should never deal with the linked list nodes.
    if(llist->size == 0) return NULL;
    return llist->head->data;
}

/** get_index
  *
  * Gets the data at the indexth node of the linked list
  * If the list is empty or if the index is invalid return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the indexth node in the linked list or NULL.
  */
void* get_index(list* llist, int index)
{
	if(index < 0 || index >= llist->size) return NULL;

	node* current_node = llist->head;
	int i = 0;
	while(i++ < index)
	{
		current_node = current_node->next;
	}
	return current_node->data;
}

/** back
  *
  * Gets the data at the "end" of the linked list
  * If the list is empty return NULL.
  *
  * @param llist a pointer to the list
  * @return The data at the last node in the linked list or NULL.
  */
void* back(list* llist)
{
    if(llist->size == 0) return NULL;
    return llist->head->prev->data;
}

/** is_empty
  *
  * Checks to see if the list is empty.
  *
  * @param llist a pointer to the list
  * @return 1 if the list is indeed empty 0 otherwise.
  */
int is_empty(list* llist)
{
    ///@note an empty list by the way we want you to implement it has a size of zero and head points to NULL.
    return (llist->size == 0);
}

/** size
  *
  * Gets the size of the linked list
  *
  * @param llist a pointer to the list
  * @return The size of the linked list
  */
int size(list* llist)
{
    return llist->size;
}

/** find_occurence
  *
  * Tests if the search data passed in is in the linked list.
  *
  * @param llist a pointer to a linked list.
  * @param search data to search for the occurence.
  * @param compare_func a pointer to a function that returns true if two data items are equal @see equal_op.
  * @return 1 if the data is indeed in the linked list 0 otherwise.
  */
int find_occurrence(list* llist, const void* search, equal_op compare_func)
{
	node* current_node = llist->head;
	for(int i = 0; i < llist->size; i++)
	{
		if(compare_func(current_node->data, search)) return 1;
		current_node = current_node->next;
	}

	return 0;
}

/** empty_list
  *
  * Empties the list after this is called the list should be empty.
  *
  * @param llist a pointer to a linked list.
  * @param free_func function used to free the node's data.
  *
  */
void empty_list(list* llist, list_op free_func)
{
    /// @note Free all of the nodes not the linked list itself.
    /// @note do not free llist.
	node* current_node = llist->head;
	for(int i = 0; i < llist->size; i++)
	{
		node* to_delete = current_node;
		current_node = current_node->next;
		free_func(current_node->data);
		free(to_delete);
	}
	llist->head = NULL;
	llist->size = 0;
}

/** traverse
  *
  * Traverses the linked list calling a function on each node's data.
  *
  * @param llist a pointer to a linked list.
  * @param do_func a function that does something to each node's data.
  */
void traverse(list* llist, list_op do_func)
{
	node* current_node = llist->head;
	for(int i = 0; i < llist->size; i++)
	{
		do_func(current_node->data);
		current_node = current_node->next;
	}
}
